#include<iostream>
#include<cstring>
using namespace std;

// 表示2*2矩阵类型
struct Matrix
{
	int data[2][2];
	
	// 构造函数
	Matrix() {}
	Matrix(int x00,int x01,int x10,int x11)
	{
		data[0][0]=x00;
		data[0][1]=x01;
		data[1][0]=x10;
		data[1][1]=x11;
	}
};

// 返回矩阵A和B相乘的结果
Matrix multiply(Matrix A, Matrix B)
{
	Matrix C;
	
	// 赋值
	memset(C.data, 0, sizeof(C.data));
	
	// 矩阵相乘
	for(int i=0; i<2; i++)
		for(int j=0; j<2; j++)
			for(int k=0; k<2; k++)
			{
				C.data[i][j] += A.data[i][k]*B.data[k][j];
				C.data[i][j] %= 10000;
			}
	return C;
}

// 求矩阵A的n次幂的快速幂算法
Matrix quick_pow(Matrix A, int n)
{
	// 置ans为单位矩阵
	Matrix ans(1,0,0,1);
	
	// 矩阵的幂
	while(n!=0)
	{
		if (n & 1)
			ans = multiply(ans, A);
		A = multiply(A, A);
		n>>=1; // n右移1位
	}
	return ans;
}

// 打印矩阵
void disp(Matrix&a)
{
	for(int i=0; i<2; i++)
	{
		for(int j=0; j<2; j++)
			printf("%4d", a.data[i][j]);
		printf("\n");
	}
}

int main()
{
	// 创建矩阵
	Matrix A(0, 1, 1, 1);
	
	// 幂
	int n=3;
	
	// 打印矩阵
	printf("A:\n");
	disp(A);
	
	// 快速幂
	Matrix ans = quick_pow(A, n);
	
	// 打印
	printf("A^%d:\n", n);
	disp(ans);
	return 0;
}

